import java.util.*;

public class Leetcode {
}

//leetcode:692:前k个高频词
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> cnt = new HashMap<>();
        //将单词放入哈希表中并记录每个单词出现的次数
        for(String word : words) {
            cnt.put(word,cnt.getOrDefault(word,0)+1);
        }

        //将哈希表中的数据放入堆中先按照按照出现次数进行排序(小根堆)，如果出现次数相同按照字典序进行排序
        PriorityQueue<Map.Entry<String,Integer>> q = new PriorityQueue<>((entry1, entry2) -> entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue());

        for(Map.Entry<String,Integer> entry : cnt.entrySet()) {
            q.offer(entry);
            //因为是要求出前k个高频单词所以哈希表中只能存放k个排好序的单词
            if(q.size() > k) {
                q.poll();
            }
        }

        //将排好序的单词出队列，并获得对应的单词
        List<String> ret = new ArrayList<>();
        while(!q.isEmpty()) {
            ret.add(q.poll().getKey());
        }

        //由于是小根堆排序所以我们出队列的顺序是前k个高频的中最小的所以我们要进行翻转
        Collections.reverse(ret);
        return ret;
    }
}

//leetcode:295:数据流的中位数
class MedianFinder {
    PriorityQueue<Integer> qMin;
    PriorityQueue<Integer> qMax;
    public MedianFinder() {
        //大根堆：用于存放中间值左边的所有元素，堆顶为左边的最大值
        qMin = new PriorityQueue<>((a,b) -> b-a);
        //小根堆：用于存放中间值右边的所有元素，堆顶为右边的最小值
        qMax = new PriorityQueue<>((a,b) -> a-b);
    }

    public void addNum(int num) {
        //如果数于左边的最大值还小还相等就将值放入左边
        if(qMin.isEmpty() || num <= qMin.peek()){
            qMin.offer(num);

            if(qMax.size()+1 < qMin.size()) {
                qMax.offer(qMin.poll());
            }
        }else{
            qMax.offer(num);
            if(qMax.size() > qMin.size()) {
                qMin.offer(qMax.poll());
            }
        }
    }

    public double findMedian() {
        //如果为奇数，左边的最大值就为中间值
        if(qMin.size() > qMax.size()){
            return qMin.peek();
        }
        //如果为偶数，就为左边最大值和右边最小值的和的一半
        return (qMax.peek() + qMin.peek()) / 2.0;
    }
}